class node{
public:
    int _key,_val;
    node* _next;
    node* _pre;
    node()
        :_key(-1),
        _val(-1),
        _next(nullptr),
        _pre(nullptr)
    {}
    node(int key,int val)
        :_key(key),
        _val(val),
        _next(nullptr),
        _pre(nullptr)
    {}
};
class LRUCache {
    node* head,*tail;
    unordered_map<int,node*> has;
    int sz;
    int capacity;
public:
    LRUCache(int capacity) {
        this->capacity=capacity;
        sz=0;
        head=new node();
        tail=new node();
        tail->_pre=head;
        head->_next=tail;
    }
    
    int get(int key) {
        if(has.count(key))
        {
            node* t=has[key];
            removeNode(t);
            addHead(t);
            return t->_val;
        }
        else{
            return -1;
        }
    }
    
    void put(int key, int value) {
        if(has.count(key))
        {
            node* t=has[key];
            removeNode(t);
            has[key]->_val=value;
            addHead(t);
        }
        else{
            node* newNode=new node(key,value);
            has[key]=newNode;
            addHead(newNode);
            sz++;
            if(sz>capacity)
            {
                node* t=removeTail();
                has.erase(t->_key);
                delete(t);
                sz--;
            }
            
        }
    }
    void addHead(node* cur)
    {
        cur->_pre=head;
        cur->_next=head->_next;
        head->_next->_pre=cur;
        head->_next=cur;
        
    }
    void removeNode(node* node)
    {
        node->_pre->_next=node->_next;
        node->_next->_pre=node->_pre;
    }
    node* removeTail()
    {
        node* t=tail->_pre;
        removeNode(t);
        return t;
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */
